package com.ljy.my_study.lintcode.回文链表;

import java.util.ArrayList;
import java.util.List;

import com.ljy.my_study.util.ListNodeUtil;
import com.ljy.my_study.util.ListNodeUtil.ListNode;

/**
 * @author James
 * @date 2019年5月11日
 */
public class TestMain {
	// Implement a function to check if a linked list is a palindrome.
	//
	// 您在真实的面试中是否遇到过这个题？
	// 样例
	// Example 1:
	//
	// Input: 1->2->1
	// output: true
	// Example 2:
	//
	// Input: 2->2->1
	// output: false
	// 挑战
	// Could you do it in O(n) time and O(1) space?
	public static void main(String[] args) {
		int[] nums= {2,1};
		ListNode head=ListNodeUtil.createListNode(nums);
		System.out.println(isPalindrome(head));
		System.out.println("-----------------------------");
		System.out.println(isPalindrome2(head));
	}

	public static boolean isPalindrome(ListNode head) {
		if(head==null) return true;
		List<ListNode> list=new ArrayList<>();
		ListNode node=head;
		while(node!=null) {
			list.add(node);
			node=node.next;
		}
		int start=0;
		int end=list.size()-1;
		while(start<=end) {
			if(list.get(start).val!=list.get(end).val) {
				return false;
			}
			start++;
			end--;
		}
		return true;
	}
	
	public static boolean isPalindrome2(ListNode head) {
		if(head==null) return true;
		ListNode reverseHead=getNewListNode(head);
		while(head!=null&&reverseHead!=null&&head.val==reverseHead.val) {
			head=head.next;
			reverseHead=reverseHead.next;
		}
		if(head==null&&reverseHead==null) return true;
		else return false;
	}
	
	public static ListNode getNewListNode(ListNode head) {
		ListNode node=head;
		ListNode nextNode=node.next;
		if(nextNode==null) {
			return node;
		} 
		ListNode newHead=new ListNode(node.val);
		ListNode nextNextNode=nextNode.next;
		if(nextNextNode==null) {
			ListNode newNode=new ListNode(nextNode.val);
			newNode.next=newHead;
			newHead=newNode;
			return newHead;
		}
		while(nextNextNode!=null) {
			ListNode newNode=new ListNode(nextNode.val);
			newNode.next=newHead;
			newHead=newNode;
			
			node=newNode;
			nextNode=nextNextNode;
			nextNextNode=nextNextNode.next;
		}
		if(nextNode!=null) {
			ListNode newNode=new ListNode(nextNode.val);
			newNode.next=newHead;
			newHead=newNode;
		}
		return newHead;
	}

}
